Abstract: A huge spectrum of Internet-scale mobile applications, for example social networking, gaming and entertainment, emergency response and crisis management, all require ef?cient and scalable All k Nearest Neighbors (AkNN) computations over millions of moving objects every few seconds to be operational. Most traditional techniques for computing AkNN queries are centralized, lacking both scalability and ef?ciency. Only recently, distributed techniques have been proposed to achieve scalability for large datasets. These batch-oriented algorithms are sub-optimal due to inef?cient data space partitioning and data replication among processing units. Algorithm Spit?re is a distributed algorithm that provides a scalable and high performance AkNN processing framework. The proposed algorithm deploys a fast load-balanced partitioning scheme along with an ef?cient replication-set selection algorithm, to provide fast main-memory computations of the exact AkNN results in a batch-oriented manner. Here the pruning ef?ciency of the Spit?re algorithm plays a pivotal role in reducing communication and response time up to an order of magnitude, compared to other state-of-the-art distributed AkNN algorithms executed in distributed main-memory.

Keywords: distributed system, memory distribution, spitfire algorithm, AKNN algorithm.